package com.exercises;

class Exercise91 {

    public static void main(String[] args) {
        System.out.println(numDecodings("2101"));
    }


    public static int numDecodings(String s) {
        if (s.startsWith("0")) return 0;

        int[] dp = new int[s.length()];
        //思路写法
        for (int i = 0; i < s.length(); i++) {
            if (i == 0) {
                dp[i] = 1;
            } else if (i == 1) {
                if (s.charAt(i) != '0') {
                    dp[i] += dp[i - 1];
                }
                String subStr = s.substring(i - 1, i + 1);
                if (Integer.parseInt(subStr) <= 26) {
                    dp[i] += 1;
                }
            } else {
                if (s.charAt(i) != '0') {
                    dp[i] += dp[i - 1];
                }
                String subStr = s.substring(i - 1, i + 1);
                if (!subStr.startsWith("0") && Integer.parseInt(subStr) <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }

        //精简写法
        dp[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                dp[i] += dp[i - 2];
            }
        }

        //省空间写法(ctrl+c)
        //a=dp[i-2]  b=dp[i-1]  c=dp[i]
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < s.length(); i++) {
            c = 0;
            if (s.charAt(i - 1) != '0') {
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                c += a;
            }
            a = b;
            b = c;
        }
//        return dp[s.length() - 1];
        return c;
    }


}
